#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

// https://leetcode.cn/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii/?envType=daily-question&envId=2025-05-29
// 3373. 连接两棵树后最大目标节点数目 II

class Solution
{
public:
    vector<vector<int>> dealEdges(vector<vector<int>> &edges)
    {
        vector<vector<int>> tree(edges.size() + 1);
        for (auto it : edges)
        {
            tree[it[0]].push_back(it[1]);
            tree[it[1]].push_back(it[0]);
        }
        return tree;
    }
    
    void dfs(vector<vector<int>> &tree, int index, int pre, bool isEven, unordered_set<int> &oddSet, unordered_set<int> &evenSet)
    {
        if (isEven)
        {
            evenSet.insert(index);
        }
        else
        {
            oddSet.insert(index);
        }
        if (tree[index].empty())
        {
            return;
        }

        for (auto curIndex : tree[index])
        {
            if (curIndex == pre)
                continue;
            dfs(tree, curIndex, index, !isEven, oddSet, evenSet);
        }
    }
    vector<int> maxTargetNodes(vector<vector<int>> &edges1, vector<vector<int>> &edges2)
    {
        vector<vector<int>> tree1 = dealEdges(edges1);
        vector<vector<int>> tree2 = dealEdges(edges2);
        // 处理右边的树
        int max2 = 0;
        unordered_set<int> oddSet;
        unordered_set<int> evenSet;
        dfs(tree2, 0, -1, false, oddSet, evenSet);
        max2 = max(oddSet.size(), evenSet.size());

        vector<int> ans(tree1.size());
        unordered_set<int> oddSet1;
        unordered_set<int> evenSet1;
        dfs(tree1, 0, -1, true, oddSet1, evenSet1);

        for (int i = 0; i < tree1.size(); i++)
        {
            if (oddSet1.find(i) != oddSet1.end())
            {
                ans[i] = oddSet1.size() + max2;
            }
            else
            {
                ans[i] = evenSet1.size() + max2;
            }
        }
        return ans;
    }
};

int main()
{
    return 0;
}